package com.clps.algorithm.chapter07.二叉树的右侧视图;

import com.clps.algorithm.chapter07.二叉树每层的最大值.TreeNode;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 给你一个二叉树，想象你站在该二叉树的右侧，从上到下你看到的节点构成二叉树的右侧试图。
 * 例如图7.6中的二叉树的右侧视图包含8、10、7三个节点。请写一个函数返回二叉树的右侧视图节点的值。
 *
 * 如图:一棵二叉树，它的右侧视图包含值分别为8、10、7三个节点。
 */
public class demo01 {

    public static void main(String[] args) {

    }


    public List<Integer> rightSideView(TreeNode root){
      List<Integer> view = new LinkedList<>();
      if(root == null){
          return  view;
      }

        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(root);
        while (!queue1.isEmpty()){
            TreeNode node = queue1.poll();

            if(node.left!=null){
                queue2.offer(node.left);
            }

            if(node.right!=null){
                queue2.offer(node.right);
            }

            if(queue1.isEmpty()){
                view.add(node.val);
                queue1 = queue2;
                queue2 = new LinkedList<>(
                );
            }
        }

        return  view;
    }
}
